package com.xj.algorithm.leetcode;

/**
 * 最大子序和--连续是隐藏条件
 */
public class L53_查找数组中的拥有最大和的连续子数组 {

    /**
     * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
     * <p>
     * 示例:
     * <p>
     * 输入: [-2,1,-3,4,-1,2,1,-5,4],
     * 输出: 6
     * 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
     * 进阶:
     * <p>
     * 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
     */

    public static void main(String[] args) {
        int[] nums = new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(maxSubArrayOffice(nums));

        int[] nums2 = new int[]{10,-7,9};
        System.out.println(maxSubArrayOffice(nums2));

        int[] nums3 = new int[]{10,-2,-1,-3,-3,10};
        System.out.println(maxSubArrayOffice(nums3));
    }

    //官方答案：贪心算法。连续的相加
    public static int maxSubArrayOffice(int[] nums) {
        int n = nums.length;
        int currSum = nums[0], maxSum = nums[0];

        for(int i = 1; i < n; ++i) {
            currSum = Math.max(nums[i], currSum + nums[i]);
            maxSum = Math.max(maxSum, currSum);
        }
        return maxSum;
    }

    //官方答案：动态数组算法，直接在原数组修改，当前最大值。本质还是3个数比最大值
    public static int maxSubArrayGood(int[] nums) {
        int n = nums.length, maxSum = nums[0];
        for(int i = 1; i < n; ++i) {
            if (nums[i - 1] > 0) {
                nums[i] += nums[i - 1];
            }
            maxSum = Math.max(nums[i], maxSum);
        }
        return maxSum;
    }
}
